# GF(2n).py
# GF(2^n)上的运算
# -*- coding: utf-8 -*-
"""
Created on 2021

@author: Ximing
"""

primitive_polynomial_dict = {
	    2:      0b111,      # x**2 + x + 1
	    3:     0b1011,      # x**3 + x + 1
	    4:    0b10011,      # x**4 + x + 1
	    5:   0b100101,      # x**5 + x**2 + 1
	    6:  0b1000011,      # x**6 + x + 1
	    7: 0b10001001,      # x**7 + x**3 + 1
	    8: (1 << 8) + 0b11101,               # x**8  + x**4  + x**3 + x**2 + 1
	    16: (1 << 16) + (1 << 12) + 0b1011,  # x**16 + x**12 + x**3 + x    + 1
	    32: (1 << 32) + (1 << 22) + 0b111,   # x**32 + x**22 + x**2 + x    + 1
	    64: (1 << 64) + 0b11011              # x**64 + x**4  + x**3 + x    + 1
	                }

def dig_to_ringelement(d):
    if d == 0:
        return "0"
    if d == 1:
        return "x**0"
    if d == None:
        return "-"
    strtemp = bin(d)
    strtemp = strtemp[::-1]
    strelements = ""
    count = 0
    if int(strtemp[0]) == 1:
        strelements = strelements + "1+"
    for i in range(1, len(strtemp)-2):
        if int(strtemp[i]) == 1:
            if i != len(strtemp)-3:
                strelements = strelements + str(i)+"**x" + "+"
            else:
                strelements = strelements + str(i)+"**x"
        count = count + 1
    strelements = strelements[::-1]
    return strelements

class GF2n(object):
    """System of Elliptic Curve"""

    def __init__(self, w):
        """elliptic curve as: (y**2 = x**3 + a * x + b) mod q
        - a, b: params of curve formula
        - q: prime number
        """
        print(w)
        self.gf_element_total_number = 1 << w
        self.primitive_polynomial = primitive_polynomial_dict[w]
        print(self.primitive_polynomial)
        self.gfilog = [1]  # g(0) = 1

        for i in range(1, self.gf_element_total_number - 1):
            temp = self.gfilog[i - 1] << 1  # g(i) = g(i-1) * g
            if temp & self.gf_element_total_number:  # if overflow, then mod primitive polynomial
                temp ^= self.primitive_polynomial  # mod primitive_polynomial in GF(2**w) == XOR
            self.gfilog.append(temp)

        assert (self.gfilog[self.gf_element_total_number - 2] << 1) ^ self.primitive_polynomial
        self.gfilog.append(None)

        self.gflog = [None] * self.gf_element_total_number
        for i in range(0, self.gf_element_total_number - 1):
            self.gflog[self.gfilog[i]] = i

    def showAllEle(self):
        print("\n 序号列，域元素 表示， 对应十进制数\n", end='')
        for i in range(0, self.gf_element_total_number):
            print("{},x**{}==,{:}，\t(-{}-)\t".format(i, i, dig_to_ringelement(self.gfilog[i]), self.gfilog[i]))

    def mul(self, a, b):
        temp = (self.gflog[a] + self.gflog[b]) % (self.gf_element_total_number-1)
        return self.gfilog[temp]

    def div(self, a, b):
        temp = (self.gflog[a] - self.gflog[b]) % (self.gf_element_total_number-1)
        return self.gfilog[temp]


if __name__ == "__main__":
    #make_gf_dict(3)
    a=int(input("please input number："))
    GF=GF2n(a)
    GF.showAllEle()
    print("GF.mul(7,12)的结果：",GF.mul(7, 12))
    print("GF.div(13,11)的结果：",GF.div(13, 11))
